//
// From Data Prefetching Championship Simulator 2
// Seth Pugsley, seth.h.pugsley@intel.com
//

/*

  This file describes an Instruction Pointer-based (Program Counter-based) stride prefetcher.  
  The prefetcher detects stride patterns coming from the same IP, and then 
  prefetches additional cache lines.

  Prefetches are issued into the L2 or LLC depending on L2 MSHR occupancy.

 */

#include "cache.h"

#define IT_ENTRY_NUM 256
#define GHB_ENTRY_NUM 256
#define PREFETCH_BEGIN 0
#define PREFETCH_DEGREE 9

class GHB_entry {
public:
    //uint8_t occupied; // if this ghbe has been used (Wasted property, perhaps reused later?)
    uint32_t it_index; // the index of linked ite in the IT
    uint64_t cl_addr; // the address of this GHB entry
    GHB_entry *prev_ptr; // the last GHB entry linked with the same IT entry
    uint32_t lru; // use LRU to evict old IP trackers

    GHB_entry () {
        //occupied = 0;
        it_index = -1;
        cl_addr = 0;
        prev_ptr = nullptr;
        lru = 0;
    }
};

class IT_entry {
public:
    uint64_t ip; // the IP being tracked
    GHB_entry *ghbe; // the linked GHB entry
    uint32_t lru; // use LRU to evict old IP trackers

    IT_entry () {
        ip = 0;
        ghbe = nullptr;
        lru = 0;
    }
};

IT_entry it[IT_ENTRY_NUM];
GHB_entry ghb[GHB_ENTRY_NUM];

void CACHE::l2c_prefetcher_initialize() 
{
    cout << "CPU " << cpu << " L2C ghb stride prefetcher" << endl;
    for (int i = 0; i < IT_ENTRY_NUM; i++) {
        it[i].lru = i;
    }
    for(int i = 0; i < GHB_ENTRY_NUM; i++) {
        ghb[i].lru = i;
    }
}

uint32_t CACHE::l2c_prefetcher_operate(uint64_t addr, uint64_t ip, uint8_t cache_hit, uint8_t type, uint32_t metadata_in)
{
    // check for an IT hit
    uint64_t cl_addr = addr >> LOG2_BLOCK_SIZE;

    int index = -1;
    for (index = 0; index < IT_ENTRY_NUM; index++) {
        if (it[index].ip == ip)
            break;
    }

    int ghb_index = -1;
    // this is a new IP that doesn't have an ite yet, so allocate one
    if (index == IT_ENTRY_NUM) {

        for (index = 0; index < IT_ENTRY_NUM; index++) {
            if (it[index].lru == IT_ENTRY_NUM - 1)
                break;
        }

        it[index].ip = ip;
        for (ghb_index = 0; ghb_index < GHB_ENTRY_NUM; ghb_index++) {
            // if (ghb[ghb_index].occupied == 0) {
            //     break;
            // }
            if (ghb[ghb_index].lru == GHB_ENTRY_NUM - 1) {
                break;
            }
        }
        // if (ghb_index == GHB_ENTRY_NUM) {
        // ghb_index = ghb_index_temp;
        // }
        it[index].ghbe = &(ghb[ghb_index]);
        it[index].ghbe->it_index = index;
        for (int i = 0; i < IT_ENTRY_NUM; i++) {
            if (it[i].lru < it[index].lru) {
                it[i].lru++;
            }
        }
        it[index].lru = 0;

        //ghb[ghb_index].occupied = 1;
        ghb[ghb_index].cl_addr = cl_addr;
        // ghb[ghb_index].prev_ptr is still nullptr because this new ite has only one ghbe for now
        for (int i = 0; i < GHB_ENTRY_NUM; i++) {
            if (ghb[i].lru < ghb[ghb_index].lru) {
                ghb[i].lru++;
            }
        }
        ghb[ghb_index].lru = 0;

        return metadata_in;
    }
    // this is an existing ite
    else {
        for (int i = 0; i < IT_ENTRY_NUM; i++) {
            if (it[i].lru < it[index].lru) {
                it[i].lru++;
            }
        }
        it[index].lru = 0;

        for (ghb_index = 0; ghb_index < GHB_ENTRY_NUM; ghb_index++) {
            // if (ghb[ghb_index].occupied == 0) {
            //     break;
            // }
            if (ghb[ghb_index].lru == GHB_ENTRY_NUM - 1) {
                break;
            }
        }
        // if (ghb_index == GHB_ENTRY_NUM) {
        //     ghb_index = ghb_index_temp;
        // }
        //ghb[ghb_index].occupied = 1;
        ghb[ghb_index].cl_addr = cl_addr;
        ghb[ghb_index].prev_ptr = it[index].ghbe;
        it[index].ghbe = &(ghb[ghb_index]);
        it[index].ghbe->it_index = index;
        for (int i = 0; i < GHB_ENTRY_NUM; i++) {
            if (ghb[i].lru < ghb[ghb_index].lru) {
                ghb[i].lru++;
            }
        }
        ghb[ghb_index].lru = 0;
    }

    // sanity check
    // at this point we should know a matching it index
    if (index == -1 || ghb_index == -1)
        assert(0);

    // calculate the stride between the current address and the last address
    // this bit appears overly complicated because we're calculating
    // differences between unsigned address variables
    int64_t stride_1 = 0, stride_2 = 0;
    if(it[index].ghbe->prev_ptr == nullptr || it[index].ghbe->prev_ptr->prev_ptr == nullptr 
        || it[index].ghbe->it_index != it[index].ghbe->prev_ptr->it_index || it[index].ghbe->prev_ptr->it_index != it[index].ghbe->prev_ptr->prev_ptr->it_index) {
        return metadata_in;
    }
    uint64_t addr_0, addr_1, addr_2;
    addr_0 = it[index].ghbe->cl_addr;
    addr_1 = it[index].ghbe->prev_ptr->cl_addr;
    addr_2 = it[index].ghbe->prev_ptr->prev_ptr->cl_addr;
    if(addr_0 > addr_1) {
        stride_1 = addr_0 - addr_1;
    }
    else {
        stride_1 = addr_1 - addr_0;
        stride_1 *= -1;
    }
    if(addr_1 > addr_2) {
        stride_2 = addr_1 - addr_2;
    }
    else {
        stride_2 = addr_2 - addr_1;
        stride_2 *= -1;
    }

    // don't do anything if we somehow saw the same address twice in a row
    if (stride_1 == 0)
        return metadata_in;

    // only do any prefetching if there's a pattern of seeing the same stride more than once
    if (stride_1 == stride_2) {

        // do some prefetching
        for (int i = PREFETCH_BEGIN; i < PREFETCH_DEGREE; i++) {
            uint64_t pf_address = (cl_addr + (stride_1 * (i + 1))) << LOG2_BLOCK_SIZE;

            // only issue a prefetch if the prefetch address is in the same 4 KB page as the current demand access address
            if ((pf_address >> LOG2_PAGE_SIZE) != (addr >> LOG2_PAGE_SIZE))
                break;

            // check the MSHR occupancy to decide if we're going to prefetch to the L2 or LLC
            if (MSHR.occupancy < (MSHR.SIZE>>1))
	            prefetch_line(ip, addr, pf_address, FILL_L2, 0);
            else
	            prefetch_line(ip, addr, pf_address, FILL_LLC, 0);
        }
    }

    return metadata_in;
}

uint32_t CACHE::l2c_prefetcher_cache_fill(uint64_t addr, uint32_t set, uint32_t way, uint8_t prefetch, uint64_t evicted_addr, uint32_t metadata_in)
{
  return metadata_in;
}

void CACHE::l2c_prefetcher_final_stats()
{
    cout << "CPU " << cpu << " L2C PC-based ghb stride prefetcher final stats" << endl;
}
